import java.util.Scanner;

//背包问题
public class test2 {

    public static int knapsack(int val[], int wt[], int W) {
        //Get the total number of items.
        //Could be wt.length or val.length. Doesn't matter
        int N = wt.length;

        //Create a matrix.
        //Items are in rows and weight at in columns +1 on each side
        int[][] V = new int[N + 1][W + 1];

        //What if the knapsack's capacity is 0 - Set
        //all columns at row 0 to be 0
        for (int col = 0; col <= W; col++) {
            V[0][col] = 0;
        }

        //What if there are no items at home.
        //Fill the first row with 0
        for (int row = 0; row <= N; row++) {
            V[row][0] = 0;
        }

        for (int item=1;item<=N;item++){
            //Let's fill the values row by row
            for (int weight=1;weight<=W;weight++){
                //Is the current items weight less
                //than or equal to running weight
                if (wt[item-1]<=weight){
                    //Given a weight, check if the value of the current
                    //item + value of the item that we could afford
                    //with the remaining weight is greater than the value
                    //without the current item itself
                    V[item][weight]=Math.max (val[item-1]+V[item-1][weight-wt[item-1]], V[item-1][weight]);
                }
                else {
                    //If the current item's weight is more than the
                    //running weight, just carry forward the value
                    //without the current item
                    V[item][weight]=V[item-1][weight];
                }
            }

        }

        //Printing the matrix
        for (int[] rows : V) {
            for (int col : rows) {
                System.out.format("%5d", col);
            }
            System.out.println();
        }

        return V[N][W];
    }

    public static void main(String[] args) {
        while (true) {
            Scanner sc = new Scanner(System.in);
            System.out.println("Please input n(0~1000) and w(0~5000):(Input 'END' to STOP)");
            String str = sc.nextLine();
            if (str.equals("END")){
                break;
            }
            else{
                String[] str1 = str.split(" ");
                int n = Integer.parseInt(str1[0]);
                int w = Integer.parseInt(str1[1]);
                if(n < 0 || n > 1000 || w < 0 || w > 5000)
                    System.out.println("Wrong number, please input once again.");
                else
                {
                    int[] value = new int[n];
                    int[] weight = new int[n];
                    boolean flag = true;
                    outer1:while(flag)
                    {
                        System.out.println("Please input v(i):");
                        String[] str2 = sc.nextLine().split(" ");
                        for (int i =0; i < n; i++){
                            value[i] = Integer.parseInt(str2[i]);
                            if (value[i] < 0 || value[i] > 10000)
                            {
                                System.out.println("Wrong number, please input once again.");
                                continue outer1;
                            }
                        }
                        flag = false;

                    }
                    flag = true;
                    outer2:while(flag)
                    {
                        System.out.println("Please input t(i):");
                        String[] str2 = sc.nextLine().split(" ");

                        for (int i =0; i < n; i++){
                            weight[i] = Integer.parseInt(str2[i]);
                            if (weight[i] < 0 || weight[i] > w)
                            {
                                System.out.println("Wrong number, please input once again.");
                                continue outer2;
                            }
                        }
                        flag = false;

                    }
                    System.out.println(knapsack(value, weight, w));


                }

            }

        }

    }
}
